package com.sakura.动态规划;

public class Code99_最小路径和 {

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(new Code99_最小路径和().minPathSum3(grid));
    }

    public int minPathSum1(int[][] grid) {
        return f1(grid, 0, 0);
    }

    // 超时
    public int f1(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length) {
            return 0;
        }
        if (i >= grid.length - 1 && j >= grid[0].length - 1) {
            return grid[i][j];
        }

        int ans1 = Integer.MAX_VALUE;
        int ans2 = Integer.MAX_VALUE;
        if (i + 1 <= grid.length - 1) {
            ans1 = f1(grid, i + 1, j);
        }
        if (j + 1 <= grid[0].length - 1) {
            ans2 = f1(grid, i, j + 1);
        }
        return Math.min(ans1, ans2) + grid[i][j];
    }

    // 从底到顶递归
    public int minPathSum2(int[][] grid) {
        return f2(grid, grid.length - 1, grid[0].length - 1);
    }
    public int f2(int[][] grid, int i, int j) {
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        int ans1 = Integer.MAX_VALUE;
        int ans2 = Integer.MAX_VALUE;
        if (i - 1>= 0) {
            ans1 = f1(grid, i - 1, j);
        }
        if (j -1 >= 0) {
            ans2 = f1(grid, i, j - 1);
        }
        return Math.min(ans1, ans2) + grid[i][j];
    }


    // 动态规划
    public int minPathSum3(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        dp[n - 1][m - 1] = grid[n - 1][m - 1];
        // 行 简单处理
        for (int i = n - 2; i >= 0; i--) {
            dp[i][m - 1] = dp[i + 1][m - 1] + grid[i][m - 1];
        }
        // 列处理
        for (int j = m - 2; j >= 0; j--) {
            dp[n - 1][j] = dp[n - 1][j + 1] + grid[n - 1][j];
        }
        // 填表
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }
        return dp[0][0];
    }
}
